#include <iostream>

typedef char VerType;
typedef int EdgeType;
void visitVer(VerType &v)
{
  printf("The vertex: %d\n", v);
}

typedef struct {
  int ver_num;
  VerType* ver_arr;
  int** edge_arr;
}GraphByMatrix;

typedef struct EdgeAdj{
  int v_id;
  EdgeType weight;
  struct EdgeAdj* nextarc;
}EdgeAdj;
typedef struct {
  VerType vex;
  EdgeAdj* firstarc;
}VerAdj;
typedef struct {
  int ver_num;
  VerAdj* ver_table;
}GraphByAdjTable;

VerType& getVex(GraphByAdjTable* G, int v_id)
{
  return G->ver_table[v_id].vex;
}

void DFS_visit(GraphByAdjTable* G, int v_id, bool* visited)
{
  if (!visited[v_id]) {
    visitVer(getVex(G, v_id));
    visited[v_id] = true;
  }

  EdgeAdj* arc = G->ver_table[v].firstarc;
  while (arc != nullptr) {
    int id = arc->v_id;
    DFS_visit(G, id, visited);
    arc = arc->nextarc;
  }
}

void DFS(GraphByAdjTable* G, int v_id)
{
  bool* visited = new bool(G->ver_num){false};
  if (visited == nullptr) {
    return;
  }

  DFS_visit(G, v_id, visited);

  delete[] visited;
  return;
}

typedef struct EdgeCross {
  int tail_id;
  int head_id;
  EdgeCross* headlink;
  EdgeCross* taillink;
}EdgeCross;
typedef struct {
  VerType vex;
  EdgeCross* firstin;
  EdgeCross* firstout;
}VerCross;
typedef struct {
  int ver_num;
  VerCross* ver_table;
}GraphByCrossTable;

